package I.堆;

import java.util.Arrays;

public class A_SmallHeap {

    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        heapsort(arr);

    }

    public static void heapsort(int[] arr){

        //首先调整无序数组
        //从最左下开始 循环
        for (int j=arr.length/2-1;j>=0;j--){
            adjust(arr,j,arr.length);
        }

        //交换调整不断循环
        for (int j= arr.length-1;j>0;j--){
            //全部调整完之后数组收尾交换
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j]=temp;

            //调整前n-1项
            adjust(arr,0,j);
        }

        System.out.println(Arrays.toString(arr));


    }

    public static void adjust(int[] arr,int i ,int len){

        int temp =arr[i];

        for (int k= 2*i+1;k<len;k=k*2+1){
            if (k+1< len && arr[k]> arr[k+1]){
                k++;
            }

            if (temp > arr[k]){
                arr[i] = arr[k];
                i = k;//递归往下走
            }else {
                break;
            }
        }

        //for循环结束 以i为根节点的树调换成功并且 i指向最后一个节点
        arr[i] = temp;
    }
}
